package com.learn.algorithm.dynamic.programming;

import java.util.Arrays;

public class LeetCode639 {

    public static int num = 1000000007;

    public static int numDecodings(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        long[] dp = new long[n + 1];
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != '0') {
                dp[i] = dp[i + 1] * (s[i] == '*' ? 9 : 1);
                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            // num num
                            if ((s[i] - '0') * 10 + (s[i + 1] - '0') < 27) {
                                dp[i] += dp[i + 2];
                            }
                        } else {
                            // num *
                            if (s[i] == '1') {
                                dp[i] += 9 * dp[i + 2];
                            }
                            if (s[i] == '2') {
                                dp[i] += 6 * dp[i + 2];
                            }
                        }
                    } else {
                        if (s[i + 1] != '*') {
                            // * num
                            if (s[i + 1] < '7') {
                                dp[i] += 2 * dp[i + 2];
                            } else {
                                dp[i] += dp[i + 2];
                            }
                        } else {
                            dp[i] += 15 * dp[i + 2];
                        }
                    }
                }
                dp[i] %= num;
            }
        }
        return (int) dp[0];
    }

    public static int numDecodings2(String s) {
        int[] dp = new int[s.length() + 1];
        Arrays.fill(dp, -1);
        return (int) f2(s.toCharArray(), 0, dp);
    }

    public static long f2(char[] s, int i, int[] dp) {
        if (i == s.length) {
            return 1;
        }
        // 1
        if (s[i] == '0') {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        // 2. i 单独转
        long ans = f2(s, i + 1, dp) * (s[i] == '*' ? 9 : 1);

        // 3. (i, i+1)一起转
        if (i + 1 < s.length) {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // num num
                    if ((s[i] - '0') * 10 + (s[i + 1] - '0') < 27) {
                        ans += f2(s, i + 2, dp);
                    }
                } else {
                    // num *
                    if (s[i] == '1') {
                        ans += 9 * f2(s, i + 2, dp);
                    }
                    if (s[i] == '2') {
                        ans += 6 * f2(s, i + 2, dp);
                    }
                }
            } else {
                if (s[i + 1] != '*') {
                    // * num
                    if (s[i + 1] < '7') {
                        ans += 2 * f2(s, i + 2, dp);
                    } else {
                        ans += f2(s, i + 2, dp);
                    }
                } else {
                    ans += 15 * f2(s, i + 2, dp);
                }
            }
        }
        ans %= num;
        dp[i] = (int) (ans);
        return ans;
    }

    public static int numDecodings1(String s) {
        return f1(s.toCharArray(), 0);
    }

    public static int f1(char[] s, int i) {
        if (i == s.length) {
            return 1;
        }
        // 1
        if (s[i] == '0') {
            return 0;
        }
        int ans = 0;
        // 2. i 单独转
        if (s[i] != '*') {
            ans = f1(s, i + 1);
        } else {
            ans = 9 * f1(s, i + 1);
        }

        // 3. (i, i+1)一起转
        if (i + 1 < s.length) {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    // num num
                    if ((s[i] - '0') * 10 + (s[i + 1] - '0') < 27) {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // num *
                    if (s[i] == '1') {
                        ans += 9 * f1(s, i + 2);
                    }
                    if (s[i] == '2') {
                        ans += 6 * f1(s, i + 2);
                    }
                }
            } else {
                if (s[i + 1] != '*') {
                    // * num
                    if (s[i + 1] < '7') {
                        ans += 2 * f1(s, i + 2);
                    } else {
                        ans += f1(s, i + 2);
                    }
                } else {
                    // * *
                    //                    if (s[i] == '1') {
                    //                        ans += 9 * f1(s, i + 2);
                    //                    }
                    //                    if (s[i] == '2') {
                    //                        ans += 6 * f1(s, i + 2);
                    //                    }
                    ans += 15 * f1(s, i + 2);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("*"));
        System.out.println(numDecodings("1*"));
        System.out.println(numDecodings("2*"));
        System.out.println(numDecodings("**1**"));
        System.out.println(numDecodings("*********"));
        System.out.println(numDecodings("7*9*3*6*3*0*5*4*9*7*3*7*1*8*3*2*0*0*6*"));
    }
}
